\onlyShort{\vspace{-0.1in}}
\section{Preliminaries}
\label{sec:prelim}
\onlyShort{\vspace{-0.1in}}
A hypergraph $\cH$ consists of a set $V(\cH)$ of $n$  (hyper)nodes and a set family $E(\cH)$ of $m$ hyperedges, each of which  is a subset of $V(\cH)$. 
We define the \emph{degree of node $u$} to be the total number of hyperedges that $u$ is contained in. 
Furthermore, we define the \emph{degree of the hypergraph}, denoted by $\Delta$, as the maximum over all hypernode degrees.
The size of each hyperedge is bounded by the \emph{dimension $\dimension$} of $\cH$; note that a hypergraph of dimension $2$ is a graph. 

We now introduce our main model of computation.
In our distributed model, $\cH$ is realized as a (standard) undirected bipartite graph $G$ with vertex sets $S$ and $C$ where $|S|=n$ and $|C|=m$.
We call $S$ the set of \emph{servers} and $C$ the set of \emph{clients} and denote this realization of a hypergraph as the \emph{server-client model}.
That is, every vertex in $S$ corresponds to a vertex in $\cH$ and every vertex in $C$ corresponds to a hyperedge of $\cH$.
For simplicity, we use the same identifiers for vertices in $C$ as for the hyperedges in $\cH$.
There exists a ($2$-dimensional) edge in $G$ from a server $u \in S$ to a client $e \in C$ if and only if $u \in e$. 
See \Cref{fig:hyper} for an example.
Thus, the degree of $\cH$ is precisely the maximum degree of the servers and the dimension of $\cH$ is given by the maximum degree of the clients.
\input{model-figures}

An alternative way to model a hypergraph $\cH$ as a  distributed network is the \emph{vertex-centric} model (cf.\ \Cref{fig:server}). Here, the nodes are exactly the nodes of $\cH$ and there exists a communication link between nodes $u$ and $v$ if and only if there exists a hyperedge $e \in E(\cH)$ such that $u, v \in e$.
Note that in this model, we assume that every node locally knows all hyperedges in which it is contained.
%We also need the following definition.\danupon{This definition should be in Prelim instead?}
%\begin{definition}[Server Graph]\label{def:underlying graph}
For any hypergraph $\cH$, we call the above underlying communication graph in  the vertex-centric model (which is a standard graph) the {\em server graph}, denoted by $G(\cH)$. 
%be a 2-dimensional simple graph whose node set is the node set of $\cH$ and we have an edge $(u, v)$ in $G(\cH)$ if and only if $u$ and $v$ are in some common hyperedge in $\cH$.
%\end{definition}
%Observe that the server graph is the underlying network in the vertex-centric model.

%We will describe our algorithms in the server-client model; we will, however, mention whenever there are differences in terms of complexity bounds w.r.t.\ to the vertex centric model. \peter{Is this the case for any of the problems?} 

We consider the standard synchronous round model (cf.\ \cite{Pel00}) of communication.
That is, each node has a unique id (arbitrarily assigned from some set of size polynomial in $n$) and executes an instance of a distributed algorithm that advances in discrete {\em rounds}.
To correctly model the computation in a hypergraph, we assume that each node knows whether it is a server or a client.
In each round every node can communicate with its neighbors (according to the edges in the server-client graph) and perform some local computation.
We do not assume shared memory and nodes do not have any a priori knowledge about the network at large.

We will consider two types of  models --- CONGEST and LOCAL \cite{Pel00}. In the CONGEST model, only a $O(\log n)$-sized
message can be sent across a communication edge per round. In the LOCAL model, there is no such restriction.
Unless otherwise stated, we use the CONGEST model in our algorithms.



\endinput

